class Solution {
public:
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int row, col;
    void solve(vector<vector<char>>& board) {
        row = board.size();
        col = board[0].size();
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (!(i != 0 && i != row - 1 && j != 0 && j != col - 1) && board[i][j] == 'O')
                    bfs(i, j, board);
            }
        }
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == '.')
                    board[i][j] = 'O';
            }
        }
    }
    void bfs(int _row, int _col, vector<vector<char>>& board)
    {
        queue<pair<int, int>> q;
        q.push({ _row, _col });
        board[_row][_col] = '.';
        while (!q.empty())
        {
            auto [x, y] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int i = x + dx[k];
                int j = y + dy[k];
                if (i >= 0 && i < row && j >= 0 && j < col && board[i][j] == 'O')
                {
                    board[i][j] = '.';
                    q.push({ i, j });
                }
            }
        }
    }
};
class Solution {
public:
    int count = 0;
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int row, col;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        row = grid.size();
        col = grid[0].size();
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (grid[i][j] == 1)
                    bfs(i, j, grid);
        return count;
    }
    typedef pair<int, int> value;
    void bfs(int _row, int _col, vector<vector<int>>& grid)
    {
        int ret = 0;
        ret++;
        queue<value> q;
        q.push({ _row, _col });
        grid[_row][_col] = 0;
        while (!q.empty())
        {
            auto [x, y] = q.front();
            q.pop();

            for (int k = 0; k < 4; k++)
            {
                int i = x + dx[k];
                int j = y + dy[k];
                if (i < row && i >= 0 && j >= 0 && j < col && grid[i][j] == 1)
                {
                    q.push({ i, j });
                    ret++;
                    grid[i][j] = 0;
                }
            }
        }
        count = max(count, ret);
    }
};